A Computer Program Listing Appendix is included with this application.
A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
1. Field of the Invention
The present invention relates generally to data processing environments and, more particularly, to system and methods for improved optimization and execution of queries accessing information stored in multiple physically separate database tables.
2. Description of the Background Art
Computers are very powerful tools for storing and providing access to vast amounts of information. Computer databases are a common mechanism for storing information on computer systems while providing easy access to users. A typical database is an organized collection of related information stored as xe2x80x9crecordsxe2x80x9d having xe2x80x9cfieldsxe2x80x9d of information. As an example, a database of employees may have a record for each employee where each record contains fields designating specifics about the employee, such as name, home address, salary, and the like.
One purpose of a database system is to answer decision support queries and support transactions. A query may be defined as a logical expression over the data and the data relationships set forth in the database, and results in identification of a subset of the database. For example, a typical query might be a request, in SQL syntax, for data values corresponding to all customers having account balances above required limits. During query processing, a database system typically utilizes one or more indexes to answer queries. Indexes are organized structures associated with the data to speed up access to particular data values (i.e., answer values). Indexes are usually stored in the database and are accessible to a database administrator as well as end users. The basic operation of database systems, including the syntax of SQL (Structured Query Language), is well documented in the technical, trade, and patent literature; see, e.g., Date, C., An Introduction to Database Systems, Volume I and II, Addison Wesley, 1990; the disclosure of which is hereby incorporated by reference.
xe2x80x9cData warehousexe2x80x9d systems represent a type of database system optimized for supporting management decision making by tracking and processing large amounts of aggregate database informationxe2x80x94that is, the data warehouse. Data warehouses contain a wide variety of data that present a coherent picture of business conditions at a single point in time. Development of a data warehouse includes development of systems to extract data from operating systems plus installation of a warehouse database system that provides managers flexible access to the data. A well-known example of a data warehouse system is Sybase(copyright) Adaptive Server(copyright) IQ (ASIQ), available from Sybase, Inc. of Dublin, Calif.
A data warehousing system typically handles large pools of historical information representing different portions of a business. These different portions may, for example, represent a number of different geographical areas, such as information relating to sales in France, Italy, Germany, and other countries or regions. The information may also represent different periods of time, such as sales in October, November, December, and so forth. A number of different products and/or business units may also be involved. Frequently, such a large quantity of information is involved that in order to store the information it must be broken down into segments that are maintained in a number of separate database tables. For example, one table may contain information regarding sales in France in December. Another table may have all sales in Italy in January. Separate tables may be created based upon geography, time period, business unit and various other factors.
Because of the large quantities of information involved in a typical data warehouse, a database administrator will typically divide the information among multiple database tables rather than including all of the information in a single table. One reason an administrator will usually avoid placing a large quantity of information into a single table is that the time taken to load to an index is a logarithmic function of the size of the table. Adding one million rows into an empty table is 100 times quicker than adding one million rows into a table that already has 100 million rows in it. An index on a 100 million-row table is quite large and adding to this index requires changing a considerable number of database pages. Thus, if an administrator is continuously loading large quantities of information on a weekly or monthly basis, it is much more efficient for the administrator to load information into a number of separate, physically smaller tables (with physically smaller indexes) than to load the information into a single large table which requires a large index to be updated. Besides enabling faster loading and indexing, the use of multiple tables also enables back up and restore operations to be handled more efficiently. For example, a manager may wish to maintain information in a data warehouse for a certain period of time (e.g., 12 months of sales data). Once a new month has been loaded in to the warehouse, an old month (e.g., the same month of the prior year) is dropped. Dropping one-twelfth of the rows from a large physical table is a very expensive operation, in terms of system performance, because it requires updating a very large index containing a large quantity of data. On the other hand, if the information is maintained in monthly tables, then the warehouse can be updated by simply dropping the tables for the old month.
Storing information in a number of separate, physically smaller tables means that one frequently has to bring multiple tables together in order to generate reports for business analysis, data mining, financial planning, or similar purposes. For example, if one stores a physical table of sales in France by week, a report that provides a view of an entire calendar quarter requires the joining of approximately thirteen weekly tables. This is typically accomplished by a SQL UnionAll operation to merge together these separate tables. An administrator may simply create a database view called xe2x80x9cQ1xe2x80x9d or xe2x80x9cFirst Quarterxe2x80x9d that looks and feels to a user of the data warehouse as if the information is stored in a single table. A user may have no knowledge that behind the scenes the administrator has chosen to store the underlying information in multiple separate tables. The user simply interacts with an object called Q1 to obtain access to the information. The problem is that if the user is summarizing information (which is implemented by the SQL GroupBy clause), the process of summarizing all of the rows that fall within a particular group requires bringing all the rows together into the summary (a physical group) before the results may be returned to the user. If the information is stored in separate tables, this means that one is required to sequentially drain all of the separate physical tables into this single summary (i.e., scanning each physical table in turn row by row to generate the result) before the summarized result is returned to the user. In other words, a serial operation is required in order to build the summary table.
In a data warehouse environment that is processing large quantities of information, this type of serial operation results in a considerable performance penalty. Analysts or other users of the data warehouse system may be delayed considerably in receiving answers to their queries. This delay makes the type of ad-hoc analysis that is typical in a data warehouse environment much less efficient and, therefore, more difficult to conduct. Adding to this problem is the fact that many businesses purchase large machines with multiple CPUs for data warehouse processing. These businesses expect this type of multiple CPU machine to return results quickly because of its ability to process information in parallel. However, because the above-described summarizing operation remains largely a serial operation, it does not take advantage of the power and capabilities of parallel processing hardware.
Current data warehouse systems may be able to process the Where clause of a query (i.e., the selection criteria) in parallel on multiple physically separate tables. However, current systems then proceed to drain (or scan) each of the rows that met the selection criteria serially in order to form a result. Typically, in executing this type of query a temporary buffer is created and the rows meeting the selection criteria are placed into the temporary buffer. Generating a result requires sequentially scanning all of the rows of the temporary buffer by first loading the buffer of rows selected from the first physical table into summarizing area, then loading the buffer of rows selected from second physical table into the summarizing area, and so forth, until all responsive data is loaded into a summary table in the summarizing area. This serial operation may mean a considerable delay in return of the results to users. Besides taking too long, this type of serial operation also fails to fully utilize the power of parallel processing hardware.
Another problem resulting from the separation of data into multiple physical tables is that this separation typically precludes use of xe2x80x9cindex-onlyxe2x80x9d query plans. If all of the data is loaded into a single table, with one index that spans all of the data, then there are classes of summary queries that can be answered using only what is in the index. These index-only plans are very efficient as they do not require access to the underlying database tables to answer a query, rather the query can be satisfied solely from key values in the index. In current systems, this type of query is not possible when the data is split amongst multiple physical tables because an index is not capable of answering a summary query involving information in a set of separate physical tables. Accordingly, once information has been broken into multiple separate physical tables, use of these efficient index-only execution plans is precluded in current systems.
Current systems have attempted to address the above problems inherent in storing information in separate tables by using the concept of xe2x80x9cmaterialized views.xe2x80x9d This approach involves executing a summarizing query offline and storing the results in a persistent temporary table. Materialized views may be used when an administrator knows in advance that a particular summarizing query will be used. When the optimizer subsequently receives that particular query (e.g., a set summary over specific data), the optimizer accesses the results stored in the temporary table to generate a response. However, this approach of using a cached version of a persistent view is only useful for a pre-defined query (i.e., where the specific query is known in advance). This may be useful for things like a standard monthly or quarterly report prepared for business executives on a regular basis. However, it is not useful for data mining or ad-hoc analysis. Data mining or ad-hoc analysis involves following hunches, taking different views of information, and exploring business data differently in order to gain a better understanding about a business. A data miner often wants to look at the same information several different ways to see what happens when certain variables are changed. The preplanned, canned approach of materialized views is not useful for this type of ad-hoc analysis.
Users in data warehousing environments need an improved method for making data in multiple physically separate tables available for ad-hoc analysis and data mining. They require an approach that makes data available for exploration in a manner that takes advantage of the parallel processing capabilities of today""s multiple CPU machines. Ideally, the approach will also enable use of efficient index-only query execution plans with information that is stored in physically separate tables with separate indexes. The present invention fulfills these and other needs.
The following definition is offered for purposes of illustration, not limitation, in order to assist with understanding the discussion that follows.
SQL: SQL stands for Structured Query Language, which has become the standard for relational database access, see e.g., Melton, J. (ed.), American National Standard ANSI/ISO/IEC 9075-2: 1999, Information Systemsxe2x80x94Database Languagexe2x80x94SQL Part2: Foundation, the disclosure of which is hereby incorporated by reference. For additional information regarding SQL in database systems, see e.g., Date, C., An Introduction to Database Systems, Volume I and II, Addison Wesley, 1990, the disclosure of which is hereby incorporated by reference.
Traditional query execution plans for grouping and aggregating queries in prior art systems involve serial operations that may cause a processing bottleneck when large quantities of data are stored in multiple separate database tables. Although data from several tables may be scanned in parallel in one step of the traditional method, subsequent grouping and aggregation steps run sequentially. The fact that the grouping and aggregation operations run sequentially, rather than in parallel, not only delays the return of query results, but also fails to utilize the capabilities of available parallel processing hardware.
The present invention includes a system providing improved methods for optimization and execution of queries aggregating information in multiple database tables. The improved method of the present invention breaks serial operations into a group of child operations that can be individually optimized and processed in parallel. The method of the present invention splits the grouping operation over a union node by pushing the grouping operation down into each input arm of the union node. Specifically, GroupBy operators are inserted into each child arm of qualifying UnionAll nodes, enabling separate physical database tables to be summarized in parallel. Each of the child GroupBy nodes concurrently groups data and generates summary results in parallel, taking advantage of available parallel processing hardware. The aggregate operators of the original master GroupBy node are modified to accept and correctly synthesize sub-aggregated results generated by each of these child nodes.
The improved methodology of pushing GroupBy nodes down into each arm of the UnionAll node enables the grouping and aggregation operation to be performed in parallel on each segment of the data. In addition to creating parallelism, query optimization is also improved as the optimizer can individually create an optimal plan for how to summarize each arm of the union node. For example, a plan may involve hash-based summarizing on one arm and sort-based summarizing on another arm depending on the query and the size of the tables involved. The methodology also includes determining whether efficient xe2x80x9cindex-onlyxe2x80x9d query execution plans can be used for particular arms to more efficiently handle the query. The system of the present invention examines each of the child GroupBy nodes of the modified query tree to determine if one or more of the GroupBy nodes can be converted into index-only plans on individual arms. The examination evaluates whether an index-only plan can be substituted in a particular node and, if so, whether or not it is advantageous (i.e., more efficient) to do so. An index-only plan is substituted in nodes where an index-only plan is valid and provides greater efficiency in executing the query. Breaking large serial operations into a series of smaller operations that can be individually optimized and processed in parallel takes advantage of the capabilities of available parallel processing hardware and optimizes system performance.